package solution.tree;

import common.TreeNode;
import common.util.TreeNodeUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : wenchao.long
 * @date : Created in 2021/07/08 16:11 周四
 * @description : 相同的树
 */
public class IsSameTreeSolution {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //return bfs(p, q);
        return dfs(p, q);
    }

    private boolean bfs(TreeNode p, TreeNode q) {
        if (p == q) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.add(p);
        q2.add(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            if (q1.size() != q2.size()) {
                return false;
            }
            TreeNode n1 = q1.remove();
            TreeNode n2 = q2.remove();
            if (n1.val != n2.val) {
                return false;
            }
            if (n1.left == null && n2.left != null) {
                return false;
            } else if (n1.left != null && n2.left == null) {
                return false;
            } else if (n1.left != null) {
                q1.add(n1.left);
                q2.add(n2.left);
            }
            if (n1.right == null && n2.right != null) {
                return false;
            } else if ((n1.right != null && n2.right == null)) {
                return false;
            } else if (n1.right != null) {
                q1.add(n1.right);
                q2.add(n2.right);
            }
        }
        return q1.isEmpty() && q2.isEmpty();
    }

    private boolean dfs(TreeNode p, TreeNode q) {
        if (p == q) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        boolean t1 = dfs(p.left, q.left);
        boolean t2 = dfs(p.right, q.right);
        return t1 && t2;
    }

    public static void main(String[] args) {
        IsSameTreeSolution solution = new IsSameTreeSolution();
        TreeNode n1 = TreeNodeUtil.create(1);
        TreeNode n2 = TreeNodeUtil.create(1, null, 2);
        System.out.println(solution.isSameTree(n1, n2));
    }

}
